package LeetCode._02算法基础.day11递归回溯;

import org.junit.Test;

/**
 * @author 挚爱之夕
 * @date 2022 - 03 - 22 - 15:45
 * @Description 给定一个m x n 二维字符网格board 和一个字符串单词word
 * 如果word 存在于网格中，返回 true ；否则，返回 false
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成
 * 其中“相邻”单元格是那些水平相邻或垂直相邻的单元格
 * 同一个单元格内的字母不允许被重复使用
 * @Version 中等
 */
public class _79单词搜索 {
    static char[][] board = {
            {'A', 'B', 'C', 'E'},
            {'S', 'F', 'C', 'S'},
            {'A', 'D', 'E', 'E'}
    };
    static String word = "ABCC";

    @Test
    public void test(){
        boolean res = exist(board, word);
        System.out.println(res);
    }
    public boolean exist(char[][] board, String word) {
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(board[i][j] == word.charAt(0)){
                    if(trackBack(board, word, i, j, 0)){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    public boolean trackBack(char[][] board, String word, int i, int j, int index){
        if(index == word.length()){
            return true;
        }
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(index)){
            return false;
        }
        char temp = board[i][j];
        //如果不修改原数组的话，可以创建一个数组记录是否走过
        board[i][j] = '1';
        //左
        if(trackBack(board, word, i, j - 1, index + 1)){
            return true;
        }

        //上
        if(trackBack(board, word, i - 1, j, index + 1)){
            return true;
        }

        //右
        if(trackBack(board, word, i, j + 1, index + 1)){
            return true;
        }

        //下
        if(trackBack(board, word, i + 1, j, index + 1)){
            return true;
        }
        board[i][j] = temp;
        return false;
    }
}
